package com.example.summary.leetcode;

import java.util.*;

/**
 * Created by wzn on 2019/6/21.
 */

//给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
//
// 示例 1:
//
// 输入: "(()"
//输出: 2
//解释: 最长有效括号子串为 "()"
//
//
// 示例 2:
//
// 输入: ")()())"
//输出: 4
//解释: 最长有效括号子串为 "()()"
//
//
public class LeetCode32 {

    public static void main(String[] args) {
        System.out.println(longestValidParentheses("())))))((())"));
    }

    public static int longestValidParentheses(String s) {
        int maxans = 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(-1);

        for (int i = 0; i < s.length(); i++) {
            String x = new String(new char[]{s.charAt(i)});
            if (x.equals("(")) {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }

        }

        return maxans;
    }
}
